Journal article
Permutations sortable by deques and by two stacks in parallel
A Elvey Price, AJ Guttmann
European Journal of Combinatorics | ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD | Published : 2017
Abstract
Recently Albert and Bousquet-Mélou (2015) obtained the solution to the long-standing problem of the number of permutations sortable by two stacks in parallel (tsip). Their solution was expressed in terms of functional equations. We show that the equally long-standing problem of the number of permutations sortable by a double-ended queue (deque) can be simply related to the solution of the same functional equations. Subject to plausible, but unproved, conditions, the radius of convergence of both generating functions is the same. Numerical work confirms this conjecture to 15 significant digits. Further numerical work suggests that the coefficients of the deque generating function behave as κd..
View full abstractGrants
Funding Acknowledgements
AJG would like to thank Mireille Bousquet-Melou for bringing her work with Michael Albert to his attention, for subsequent discussions, and a careful reading of the first version of this article. We would also like to thank Kilian Raschel for telling us of his exponent conjecture, and permitting us to publish it. We are grateful to Jay Pantone for employing his algorithm to search for a differentially algebraic generating function, and for a careful reading of the manuscript. We would also like to thank Nathan Clisby for writing a multiple-precision differential approximant program, and applying it to the series we generated. AEP would like to acknowledge the support of the ARC Centre of Excellence for Mathematics and Statistics of Complex Systems (MASCOS) (Grant No. CE0348217).